1. Field of Invention
The present invention relates generally to mass digital data storage systems. More particularly, the present invention relates to systems and methods for efficiently writing to a block of flash memory.
2. Description of the Related Art
The use of non-volatile memory systems such as flash memory storage systems is increasing due to the compact physical size of such memory systems, and the ability for non-volatile memory to be repetitively reprogrammed. The compact physical size of flash memory storage systems facilitates the use of such storage systems in devices which are becoming increasingly prevalent. Devices which use flash memory storage systems include, but are not limited to, digital cameras, digital camcorders, digital music players, handheld personal computers, and global positioning devices. The ability to repetitively reprogram non-volatile memory included in flash memory storage systems enables flash memory storage systems to be used and reused.
In general, flash memory storage systems may include flash memory cards and flash memory chip sets. Flash memory chip sets generally include flash memory components and a controller components. Typically, a flash memory chip set may be arranged to be assembled into an embedded system. The manufacturers of such assemblies or host systems typically acquire flash memory in component-form, as well as other components, then assemble the flash memory and the other components into a host system.
As shown in FIG. 1a, within a file system, memory 10 is effectively divided into a system or directory area 12 and a data area 14. System area 12 generally includes root directories and file allocation tables (FATs), while data files are typically included in data area 14. A file system may write data in sectors, e.g., one page at a time, into system area 12, while writing data in clusters, e.g., multiple pages at a time, into data area 14. The size of each cluster, which is generally the minimum size of a file that is associated with data area 14, may vary. For example, in an overall system which is running either a Windows or a DOS system, a cluster may be sized to include approximately four to approximately 256 pages.
Any updates associated with a logical block, or a block that is associated with a file system, are effectively propagated to the flash media where a physical block is mapped to the logical block. FIG. 1b is a diagrammatic representation of a mapping between a logical block and a physical block of a flash media. A logical block 52 includes a plurality of pages which are each mapped to pages of a physical block 54 such that when a page associated with logical block 52 is updated, the update is written into physical block 54.
When a page, e.g., a logical page, is updated, a physical block with which the page is associated is written to. Conventionally, a block may be written to in a “fixed” manner or in a “random” manner. When a block is written to in a fixed manner, a page is written into a block at a corresponding page offset. As shown in FIG. 2a, when a logical block page 214 is updated, contents associated with the logical block page 214 are generally written into a corresponding page 218 within a physical block 210. For example, when logical block page 214 corresponds to physical block page 218h, and physical block page 218h is available, the contents of logical block page 214 may be written into physical block page 218h. When physical block page 218h is available, the indication is that there have effectively been no pages 218 written in block 210 that have a higher page number than physical block page 218h. 
In the event that there have been pages 218 written in block 210 that have a higher page number than a logical block page with contents which are to be written, then when block 210 is arranged to be written to in a fixed manner, the contents of the logical block page may not be written into block 210. To write a lower page number after the higher page has been written into the flash memory is an “out-of-sequence” write operation. As will be understood by those skilled in the art, some flash media do not allow for this type of operation. Therefore, the contents of the logical block page as well as contents of pages 218 are written into a new block. FIG. 2b is a diagrammatic representation of an old block, e.g., block 210 of FIG. 2a, and a new block which is arranged to accommodate the contents of the old block. When contents of a logical block page 234 are to be written into a physical block in a fixed manner, it is determined whether block 210, i.e., a current block, may be written into. If logical page 234 has a lower page number than is available in block 210, then the contents of logical page 234 may not be written into block 210. In other words, if a physical page 218 with a corresponding page offset to logical block 234 is not available, e.g., has already been written to, then a new physical page 230 generally must be obtained to enable the contents of logical page 234 to be written.
Since logical block 234 corresponded to page 218c of physical block 210, when block 230 is obtained, the contents of pages 218 are generally copied into corresponding pages 238 of physical block 230, except for the contents of page 218c. Instead of copying the contents of page 218c into page 238c, the contents of logical block 234 are copied into page 238c. Hence, after a copy or write operation, page 238a, page 238b, and pages 238d-238g contain the contents of page 218a, page 218b, and pages 218d-g, respectively, while page 238c contains the contents associated with logical page 234. Once block 230 has been written to, then block 210 may be erased.
Writing to a block in a fixed manner is generally efficient when a page with a corresponding page offset is available within the block for a page that is being written. However, when a page with a corresponding page offset is not available to be written into, then even if there are available pages within the block, a new block generally must be obtained to enable the write operation to be completed. Obtaining a new block consumes a significant amount of computational overhead, copy operations which copy contents into the new block and erase operations which erase an old block typically must be run. As will appreciated by those skilled in the art, such operations, particularly write and erase operations, are relatively expensive.
In lieu of a fixed manner or writing to a block, a random manner may instead be implemented to write data to a block. Contents associated with substantially any logical page may be written into the next available page space in a block when blocks are written to in a random manner. With reference to FIG. 3, a random manner of writing data to a block will be described. When contents of a logical block page 314 are to be written into a physical block 310 and there are available pages 318 within block 310, then the contents of logical block page 314 may be written into the next sequential available page 318. For example, the contents of logical page 314a may be written into page 318h, while the contents of logical page 314b may be written into page 318i. 
It should be appreciated that although logical page 314b may correspond to page 318c, updated contents of logical page 314b may be written into page 318i if page 318i is the next available page in block 310. When logical page 314 is essentially to be read, then it is generally necessary to identify page 318i within block 310 as containing the latest contents associated with logical page 314b. As shown, when page 318i is the last page in block 310, identifying page 318i as containing contents associated with logical page 314b may require reading all of block 310 and, hence, may require a relatively high number of read operations. Reading through substantially all of block 310 in order to access contents associated with logical page 314b may be relatively time-consuming. Although there are techniques which use overall system memory or flash memory for caching information relating to pages 318 and contents of pages 318 such that the number of read operations needed to locate and access contents associated with logical pages such as logical pages 314 may be reduced, such techniques increase memory requirements of the overall system or, more specifically, software executing within the overall system.
Therefore, what are desired are a hybrid method and an apparatus for efficiently enabling pages associated with physical blocks to be written and to be accessed. That is, what is needed is a hybrid system which utilizes both fixed and random processes to enable pages within a block to be efficiently written to and easily accessed, substantially without requiring relatively frequent block erasures or a relatively large number of read operations.